package com.leetcode;

public class leetcode45 {
    public static void main(String[] args) {
        final Solution solution = new Solution();
//        int[] arr = {7,0,9,6,9,6,1,7,9,0,1,2,9,0,3};
        int[] arr = {2,3,1,1,4};
        int a = solution.jump(arr);
        System.out.println(a);
    }

    static  class Solution {
        public int jump(int[] nums) {
            if(nums.length == 1){
                return 0;
            }
            int curDistance = 0; // 当前覆盖最远距离下标
            int ans = 0; // 记录⾛的最⼤步数
            int nextDistance = 0; // 下⼀步覆盖最远距离下标
            for (int i = 0; i < nums.length; i++) {
                nextDistance = Math.max(nums[i] + i, nextDistance); // 更新下⼀步覆盖最远距离下标
                if (i == curDistance) { // 遇到当前覆盖最远距离下标
                    if (curDistance != nums.length - 1) {
                        ans++; // 需要⾛下⼀步
                        curDistance = nextDistance;
//                        if (nextDistance >= nums.length - 1) break;
                    } else break;
                }
            }
            return ans;
        }
    }
}


